get-the-solution

Discrete Wavelet transformation

By
on Regards: education; Article; python; sip;

Discrete Wavelet transformation

Wavelets

This text is from the category SIP (Signal and image processing). Previous text Discrete cosine transform

Beside the discrete fourier transformation, which disassembles the signal in periodic sin waves, there exists other types of transformations like the

which can be used to analyze the spectrum of a signal.

Signals which change there spectral properties over time, like the following example, it makes sense to find an better or enhanced method to transform the signal to the frequency domain.

Fig. 1.

The above signals oscillation is from t0 to t1 fast, but the oscillation gets much slower from t1 to t2. Doing the “normal” discrete time fourier transformation to retrieve the amplitude spectrum |X(ω)| it would look like the following plot.

Fig. 2.

Without the plot of x(t) and only observing the plot |X(ω)| you can get the wrong imagination that the signal looks like a fast and a slow oscillation on top of each other.

Short discrete (time) fourier transformation

For this kind of situations it makes sense to analyse the signal in a more dynamic kind of fashion.

Idea: Perform short but multiple discrete time fourier transformation (STFT) using windows (moving and potentially overlapping) windows -> Short time fourier transformation (S(T)FT). This can be expressed like the following:

$X(\omega_i,\tau)=\sum_{\infty}^{n=-\infty}w[n-\tau]\cdot x[n]\cdot e^{-j\omega n}$

w[n]…some window of length M.

Plotting the |X(ωi)| as Time-frequency plane results in a 2d plot. The time resolution is determined by the window length M. For example assume M=100 and fs = 100Hz.

Fig. 3. Fig. 4.

In the left figure (Fig. 3.) you can see that the resolution is constant. You can choose higher frequency resolution but then you haver a lower time resolution and visa verse. The frequency resolution is always constant along the frequency-axes. With the above fs and M the frequency resolution would be 1 Hz.

We know that slow oscillation tend to change the amplitude slowly and fast oscillations tend to change the amplitude quickly. In some situations like in image signals or time signals it makes sense to drop the constant grid. Like in the right figure (Fig. 4.) (time frequency plane with other grid). It illustrates that low frequencies got a long time resolution and as you move up to higher frequencies the time resolution gets doubled and the frequency resolution gets halved.

The discrete Wavelet transformation (DWT)

The DWT is able to create such an output as shown in figure 4 (right image). The DWT consists of a set of transformations. How the grid will look like depends on the used mother wavelet. The mother mother wavelet h[n] of length M, is define as:

$h_{m,k}[n]=2^{\frac{-m}{k}}\cdot h[2^{-m}\cdot n-k\cdot2^{-m}\cdot M];m,k\in\mathbb{N}$

2−m… scaling of mother wavelet

k… shift of wavelet of length M

The index for hm, k has two scaling factors m and k. The scaling factor k is a shift in time and the m scales the mother wavelet in frequency.

The DWT is given by

$X[m,k]=2^{\frac{-m}{2}}\cdot\sum_{n=-\infty}^{\infty} x[n]\cdot h[2^{-m}n-k2^{-m}M]$

h[2−mn−k2−mM]…basis function

m… frequency parameter k… position

How do we design a mother wavelet that has the properties:

  •  < hm, k[n], hm′, k′[n] >  = δm, k ⋅ δm′, k′
  • orthogonal basis (inner product of  < hm, k[n], hm′, k′[n]> should be zero)
  • inner product of  < hm, k[n], hm′, k′[n]> should be one if we have same scaling and same position

With orthogonal projection we can (as we did with the D(T)FT) from our time domain to the wavelet domain.

There are different mother wavelets which provide the above property. Depending on which mother wavelets we wanted to use (for example haar wavelet) we get different instances of the discrete wavelet transform.

An other way to describe the wavelet transformation would be the following. We have a signal and we use the mother wavelet as some kind of a template. The mother wavelet or the so called template is based on for example the haar wavelet, mexican hat, or another famous wavelet function. The template will be then next scaled and shifted over the original signal in a way, that the scaled and shifted template matches best and close as possible to the original signal.

To summarize: With the wavelet transformation we try to find a transformation with m and k, which describes the original signal using the wavelets. The transformation of the DWT can be viewed as FIR filtering (original signal is multiped with the wavelets). Wavelet corresponds to a high pass filter and the scaling corresponds as low pass filter.

Hint: For finding the right template you may know some characteristics of the original signal. For example the original signal contain low frequencies you can choose a template which consists also of low frequencies.

The Haar wavelet

$h[n]=\begin{cases} 1;0\le n\le\frac{M}{2} \\ -1;\frac{M}{2}<n<M \\ 0; otherwise \end{cases}$

Fig. 5.

Any set of N paris of (m,k) gives a orthonormal basis hm, k[n]

Mexican hat / Ricker wavelet

$h[n]=\frac{2}{\sqrt{3\cdot\sigma}\cdot\pi^{1/4}}(1-({\frac{n}{\sigma}})^2)\cdot e^{-\frac{n^2}{2\cdot\sigma^2}}$

The mexican hat wavelets gives rise to an orthonormal basis but has infinite support.

Daubechies

Compact support (final length), gives rise to orthonormal basis, but has no analytics expression.

Summary: Design mother wavelet shift and translate, and every shift and translation gives a new basis function.

Sources:

  • transcript of course signal image processing
  • transcript of course biosignal